'Weak Dependency Graph [60.0]'
------------------------------
Answer: YES(?,O(n^1))
Input Problem: innermost runtime-complexity with respect to
Rules:
{ norm(nil()) -> 0()
, norm(g(x, y)) -> s(norm(x))
, f(x, nil()) -> g(nil(), x)
, f(x, g(y, z)) -> g(f(x, y), z)
, rem(nil(), y) -> nil()
, rem(g(x, y), 0()) -> g(x, y)
, rem(g(x, y), s(z)) -> rem(x, z)}
Details:
We have computed the following set of weak (innermost) dependency pairs:
{ norm^#(nil()) -> c_0()
, norm^#(g(x, y)) -> c_1(norm^#(x))
, f^#(x, nil()) -> c_2()
, f^#(x, g(y, z)) -> c_3(f^#(x, y))
, rem^#(nil(), y) -> c_4()
, rem^#(g(x, y), 0()) -> c_5()
, rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
The usable rules are:
{}
The estimated dependency graph contains the following edges:
{norm^#(g(x, y)) -> c_1(norm^#(x))}
==> {norm^#(g(x, y)) -> c_1(norm^#(x))}
{norm^#(g(x, y)) -> c_1(norm^#(x))}
==> {norm^#(nil()) -> c_0()}
{f^#(x, g(y, z)) -> c_3(f^#(x, y))}
==> {f^#(x, g(y, z)) -> c_3(f^#(x, y))}
{f^#(x, g(y, z)) -> c_3(f^#(x, y))}
==> {f^#(x, nil()) -> c_2()}
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
==> {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
==> {rem^#(g(x, y), 0()) -> c_5()}
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
==> {rem^#(nil(), y) -> c_4()}
We consider the following path(s):
1) { rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))
, rem^#(nil(), y) -> c_4()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {rem^#(nil(), y) -> c_4()}
Weak Rules: {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{rem^#(nil(), y) -> c_4()}
and weakly orienting the rules
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{rem^#(nil(), y) -> c_4()}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
s(x1) = [1] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_4() = [0]
c_5() = [0]
c_6(x1) = [1] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ rem^#(nil(), y) -> c_4()
, rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
The given problem does not contain any strict rules
2) { rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))
, rem^#(g(x, y), 0()) -> c_5()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {rem^#(g(x, y), 0()) -> c_5()}
Weak Rules: {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
We apply the weight gap principle, strictly orienting the rules
{rem^#(g(x, y), 0()) -> c_5()}
and weakly orienting the rules
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{rem^#(g(x, y), 0()) -> c_5()}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
s(x1) = [1] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_4() = [0]
c_5() = [0]
c_6(x1) = [1] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ rem^#(g(x, y), 0()) -> c_5()
, rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
The given problem does not contain any strict rules
3) { norm^#(g(x, y)) -> c_1(norm^#(x))
, norm^#(nil()) -> c_0()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {norm^#(nil()) -> c_0()}
Weak Rules: {norm^#(g(x, y)) -> c_1(norm^#(x))}
Details:
We apply the weight gap principle, strictly orienting the rules
{norm^#(nil()) -> c_0()}
and weakly orienting the rules
{norm^#(g(x, y)) -> c_1(norm^#(x))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{norm^#(nil()) -> c_0()}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [1] x1 + [1]
c_0() = [0]
c_1(x1) = [1] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ norm^#(nil()) -> c_0()
, norm^#(g(x, y)) -> c_1(norm^#(x))}
Details:
The given problem does not contain any strict rules
4) { f^#(x, g(y, z)) -> c_3(f^#(x, y))
, f^#(x, nil()) -> c_2()}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(x, nil()) -> c_2()}
Weak Rules: {f^#(x, g(y, z)) -> c_3(f^#(x, y))}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(x, nil()) -> c_2()}
and weakly orienting the rules
{f^#(x, g(y, z)) -> c_3(f^#(x, y))}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(x, nil()) -> c_2()}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_2() = [0]
c_3(x1) = [1] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules:
{ f^#(x, nil()) -> c_2()
, f^#(x, g(y, z)) -> c_3(f^#(x, y))}
Details:
The given problem does not contain any strict rules
5) {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
s(x1) = [1] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [1] x1 + [1] x2 + [8]
c_4() = [0]
c_5() = [0]
c_6(x1) = [1] x1 + [3]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {rem^#(g(x, y), s(z)) -> c_6(rem^#(x, z))}
Details:
The given problem does not contain any strict rules
6) {norm^#(g(x, y)) -> c_1(norm^#(x))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {norm^#(g(x, y)) -> c_1(norm^#(x))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{norm^#(g(x, y)) -> c_1(norm^#(x))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{norm^#(g(x, y)) -> c_1(norm^#(x))}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [1] x1 + [1]
c_0() = [0]
c_1(x1) = [1] x1 + [3]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {norm^#(g(x, y)) -> c_1(norm^#(x))}
Details:
The given problem does not contain any strict rules
7) {f^#(x, g(y, z)) -> c_3(f^#(x, y))}
The usable rules for this path are empty.
We have oriented the usable rules with the following strongly linear interpretation:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [0] x1 + [0] x2 + [0]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_2() = [0]
c_3(x1) = [0] x1 + [0]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
We have applied the subprocessor on the resulting DP-problem:
'Weight Gap Principle'
----------------------
Answer: YES(?,O(n^1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {f^#(x, g(y, z)) -> c_3(f^#(x, y))}
Weak Rules: {}
Details:
We apply the weight gap principle, strictly orienting the rules
{f^#(x, g(y, z)) -> c_3(f^#(x, y))}
and weakly orienting the rules
{}
using the following strongly linear interpretation:
Processor 'Matrix Interpretation' oriented the following rules strictly:
{f^#(x, g(y, z)) -> c_3(f^#(x, y))}
Details:
Interpretation Functions:
norm(x1) = [0] x1 + [0]
nil() = [0]
0() = [0]
g(x1, x2) = [1] x1 + [1] x2 + [8]
s(x1) = [0] x1 + [0]
f(x1, x2) = [0] x1 + [0] x2 + [0]
rem(x1, x2) = [0] x1 + [0] x2 + [0]
norm^#(x1) = [0] x1 + [0]
c_0() = [0]
c_1(x1) = [0] x1 + [0]
f^#(x1, x2) = [1] x1 + [1] x2 + [1]
c_2() = [0]
c_3(x1) = [1] x1 + [3]
rem^#(x1, x2) = [0] x1 + [0] x2 + [0]
c_4() = [0]
c_5() = [0]
c_6(x1) = [0] x1 + [0]
Finally we apply the subprocessor
'Empty TRS'
-----------
Answer: YES(?,O(1))
Input Problem: innermost DP runtime-complexity with respect to
Strict Rules: {}
Weak Rules: {f^#(x, g(y, z)) -> c_3(f^#(x, y))}
Details:
The given problem does not contain any strict rules